#pragma once
#include<iostream>
#include<vector>
using namespace std;

//状态
enum Status
{
    EMPTY,
    DELETE,
    EXIST
};
template<class K>
struct Hash
{
    //注意：返回类型为size_t，遇到负数也可以处理
    size_t operator()(const K& val)
    {
        return val;
    }
};
//偏特化
template<>
struct Hash<string> 
{
    size_t operator()(const string& s)
    {
        // BKDR
        size_t value = 0;
        for (auto ch : s)
        {
            value *= 31;
            value += ch;
        }
        return value;
    }
};
template<class K,class V>
struct HashNode
{
    pair<K, V> kv;
    Status status;
    HashNode(const pair<K, V>& k)
        :kv(k), status(EMPTY)
    {}
    HashNode()
        :status(EMPTY)
    {}
};

template<class K,class V,class HashFunc = Hash<K>>
class CloseHash
{
public:
    CloseHash()
        :n(0) //不给n初始化就是随机值
    {}
    bool Insert(const pair<K,V>& k)
    {
        HashNode<K, V>* ret = find(k.first);
        if (ret != nullptr)
        {
            return false;
        }
        //检查是否需要扩容-大小为0 || 负载因子>0.7
        if (tables.size() == 0 || n*10 / tables.size() >= 7)
        {
            CloseHash<K, V, HashFunc> newHash;
            //注意：这里是resize,不能是reserve！！！容量属于你，但是你暂时不能用这块空间
            newHash.tables.resize(tables.size() == 0 ? 10 : tables.size() * 2);
            for (int i = 0; i < tables.size(); i++)
            {
                if(tables[i].status == EXIST)
                    newHash.Insert(tables[i].kv);
            }
            tables.swap(newHash.tables);
        }
        size_t start = HashFunc()(k.first) % tables.size();;
        size_t i = 0;
        size_t index = start;
        while (tables[index].status == EXIST) //找到DELETE || EMPTY位置插入
        {
            i++;
            index = start + i;//线性探测
            //index = start + i * i;//二次探测
            index %= tables.size();
        }
        tables[index].kv = k;
        tables[index].status = EXIST;
        n++;
        return true;
    }
    bool Erase(const K& key)
    {
        HashNode<K, V>* ret = find(key);
        if (ret != nullptr)
        {
            ret->status = DELETE;
            n--;
            return true;
        }
        else
            return false;
    }
    HashNode<K,V>* find(const K& key)
    {
        if (tables.size() == 0)
            return nullptr;
        HashFunc hf;
        size_t start = hf(key) % tables.size();
        size_t i = 0;
        size_t index = start;
        while (tables[index].status != EMPTY)
        {
            //值匹配 && 状态是存在
            if (tables[index].kv.first == key && tables[index].status == EXIST)
            {
                return &tables[index];
            }
            i++;
            index = start + i;
            //index = start + i * i; //二次探测
            index %= tables.size();
        }
        return nullptr;
    }
    vector<HashNode<K, V>>& GetTable()
    {
        return tables;
    }
private:
    vector<HashNode<K,V>> tables;
    size_t n = 0;//给缺省值
};
